package listbyorder.access101_200.test174;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/14 14:44
 */
public class Solution1 {

    // 地下城游戏
    public int calculateMinimumHP(int[][] dungeon) {
        int row = dungeon.length;
        int col = dungeon[0].length;
        int[][] dp = new int[row][col];
        dp[row - 1][col - 1] = dungeon[row - 1][col - 1] >= 0 ? 1 : 1 - dungeon[row - 1][col - 1];
        for (int i = row - 2; i >= 0; i--) {
            dp[i][col - 1] = dungeon[i][col - 1] >= dp[i + 1][col - 1] ? 1 : dp[i + 1][col - 1] - dungeon[i][col - 1];
        }
        for (int j = col - 2; j >= 0; j--) {
            dp[row - 1][j] = dungeon[row - 1][j] >= dp[row - 1][j + 1] ? 1 : dp[row - 1][j + 1] - dungeon[row - 1][j];
        }

        for (int i = row - 2; i >= 0; i--) {
            for (int j = col - 2; j >= 0; j--) {
                int e1 = dungeon[i][j] >= dp[i + 1][j] ? 1 : dp[i + 1][j] - dungeon[i][j];
                int e2 = dungeon[i][j] >= dp[i][j + 1] ? 1 : dp[i][j + 1] - dungeon[i][j];
                dp[i][j] = Math.min(e1, e2);
            }
        }
        return dp[0][0];
    }
}
